import java.io.IOException;
import java.util.Vector;

public class Network {
  public static int MAX_DEG = 10000;

  public Integer[] degrees = new Integer[MAX_DEG];
  public Integer[] cumDegrees = new Integer[MAX_DEG];
  public Vector<Integer> degs_;
  
  public int maxDeg_;
  public int cumSum_;
  public int numNodes_;
  
  public static class Similarity {
    public Double maxDiff;
    public Double avgDiff;
  }

  public Network(Vector<Integer> degs) throws IOException {
    degs_ = new Vector<Integer>();
    degs_.addAll(degs);
    
    initialize();
  }
  
  public void initialize() throws IOException {
    for (int i = 0; i < degrees.length; ++i) {
      degrees[i] = 0;
    }
    
    maxDeg_ = cumSum_ = 0;
    for (int i = 0; i < degs_.size(); ++i) {
      degrees[degs_.get(i)]++;
      
      cumSum_ += degs_.get(i);
      maxDeg_ = Math.max(maxDeg_, degs_.get(i));
    }
    
    int cum = 0;
    cumDegrees[0] = 0;
    for (int i = 1; i <= maxDeg_; ++i) {
      cumDegrees[i] = cumDegrees[i-1] + degrees[i];
    }
    
    numNodes_ = degs_.size();
    if (cumDegrees[maxDeg_] != numNodes_) System.err.println("cumDegrees[maxDeg_] != numNodes_");
  }
  
  public static Similarity calculateSim1(Network n1, Network n2) {
    int d = 0;
    
    Double maxDiff = -1.0;
    Double avg = 0.0;
    Double sum = 0.0;

    while (d < n1.maxDeg_ || d < n2.maxDeg_) {
      Double p1 = 0.0;      
      if (d >= n1.maxDeg_) {
        p1 = 1.0;
      } else {
        p1 = (double)n1.cumDegrees[d] / (double)n1.numNodes_;
      }
      
      Double p2 = 0.0;      
      if (d >= n2.maxDeg_) {
        p2 = 1.0;
      } else {
        p2 = (double)n2.cumDegrees[d] / (double)n2.numNodes_;
      }
      
      Double diff = Math.abs(p1 - p2);
      
      sum += diff;
      maxDiff = Math.max(diff, maxDiff);
      
      d++;
    }
    
    avg = sum / (double) d;
    
    Similarity sm = new Similarity();
    sm.maxDiff = maxDiff;
    sm.avgDiff = avg;
    return sm;
  }
  
  public static Similarity calculateSim2(Network n1, Network n2) {
    Double maxDiff = -1.0;
    Double avg = 0.0;
    Double sum = 0.0;
    
    int steps = 20;
    int d;
    for (int s = 1; s <= steps; ++s) {
      d = n1.maxDeg_ / s;
      
      Double p1 = 0.0;
      if (d >= n1.maxDeg_) {
        p1 = 1.0;
      } else {
        p1 = (double)n1.cumDegrees[d] / (double)n1.numNodes_;
      }
      
      d = n2.maxDeg_ / s;
      Double p2 = 0.0;
      if (d >= n2.maxDeg_) {
        p2 = 1.0;
      } else {
        p2 = (double)n2.cumDegrees[d] / (double)n2.numNodes_;
      }
      
      Double diff = Math.abs(p1 - p2);
      
      sum += diff;
      maxDiff = Math.max(diff, maxDiff);
    }
    
    avg = sum / (double) steps;
    
    Similarity sm = new Similarity();
    sm.maxDiff = maxDiff;
    sm.avgDiff = avg;

    return sm;
  }
  
  
}
